#define _CRT_SECURE_NO_WARNINGS	

#include<stdio.h>
#include<queue>

using namespace std;

int Get_MaxNum_Figure(int arr[], int len)
{
    int rel = arr[0];
    for (int i = 1; i < len; i++)
        rel = arr[i] > rel ? rel = arr[i] : rel;

    if (!rel)
        return 1;

    int cnt = 0;
    while (rel)
    {
        cnt++;
        rel /= 10;
    }

    return cnt;
}

int Get_Num_Digit(int x, int index)
{
    return x / (int)pow(10, index) % 10;
}

void Radix(int arr[], int len, int index)
{
    std::queue<int> qu_arr[10];
    for (int i = 0; i < len; i++)
    {
        int w = Get_Num_Digit(arr[i], index);
        qu_arr[w].push(arr[i]);
    }

    int k = 0;
    for (int i = 0; i < 10; i++)
        while (!qu_arr[i].empty())
        {
            arr[k++] = qu_arr[i].front();
            qu_arr[i].pop();
        }
}

void Radix_Sort(int arr[], int len)
{
    int index = Get_MaxNum_Figure(arr, len);

    for (int i = 0; i < index; i++)
        Radix(arr, len, i);
}


int main()
{
    int arr[9] = { 98,87,76,65,54,43,32,21,10 };
    Radix_Sort(arr, 9);
    for (int i = 0; i < 9; i++)
        printf("%d ", arr[i]);
    return 0;
}